//
// Created by bleedingfight on 2020/6/25.
//
#include "findTargetSumWays.h"
int maxSum(std::vector<int>& nums) {
  int r = 0;
  for (auto e : nums) r += std::abs(e);
  return r;
}

int findTargetSumWaysOpt(std::vector<int>& nums, int S) {
  const int N = nums.size();
  int maxOffset = maxSum(nums);
  if (std::abs(S) > maxOffset) return 0;
  std::vector<std::vector<int>> dp =
      std::vector<std::vector<int>>(N, std::vector<int>(maxOffset * 2 + 1, 0));
  if (nums[0] == 0) {
    dp[0][maxOffset] = 2;
  } else {
    dp[0][maxOffset - nums[0]] = 1;
    dp[0][maxOffset + nums[0]] = 1;
  }
  for (int r = 1; r < N; r++) {
    for (int c = 0; c < 2 * maxOffset + 1; c++) {
      int left = c - nums[r] >= 0 ? c - nums[r] : 0;
      int right = c + nums[r] <= 2 * maxOffset ? c + nums[r] : 0;
      dp[r][c] = dp[r - 1][left] + dp[r - 1][right];
    }
  }
  return dp[N - 1][S + maxOffset];
}
int findTargetSumWays(std::vector<int>& nums, int S) {
  const int N = nums.size();
  int maxOffset = maxSum(nums);
  if (std::abs(S) > maxOffset) return 0;
  std::vector<int> dp = std::vector<int>(2 * maxOffset + 1, 0);
  std::vector<int> next = std::vector<int>(2 * maxOffset + 1, 0);

  if (nums[0] == 0) {
    dp[maxOffset] = 2;
  } else {
    dp[maxOffset - nums[0]] = 1;
    dp[maxOffset + nums[0]] = 1;
  }

  for (int r = 1; r < N; r++) {
    for (int c = 0; c < 2 * maxOffset + 1; c++) {
      int left = c - nums[r] >= 0 ? c - nums[r] : 0;
      int right = c + nums[r] <= 2 * maxOffset ? c + nums[r] : 0;
      next[c] = dp[left] + dp[right];
    }
    dp = next;
  }
  return dp[S + maxOffset];
}
